{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Floored Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #binary-search #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #二分查找 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumOfFlooredPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #向下取整数对和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，请你返回所有下标对 <code>0 &lt;= i, j &lt; nums.length</code> 的 <code>floor(nums[i] / nums[j])</code> 结果之和。由于答案可能会很大，请你返回答案对<code>10<sup>9</sup> + 7</code> <strong>取余</strong> 的结果。</p>\n",
    "\n",
    "<p>函数 <code>floor()</code> 返回输入数字的整数部分。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,5,9]\n",
    "<b>输出：</b>10\n",
    "<strong>解释：</strong>\n",
    "floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0\n",
    "floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1\n",
    "floor(5 / 2) = 2\n",
    "floor(9 / 2) = 4\n",
    "floor(9 / 5) = 1\n",
    "我们计算每一个数对商向下取整的结果并求和得到 10 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [7,7,7,7,7,7,7]\n",
    "<b>输出：</b>49\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-floored-pairs](https://leetcode.cn/problems/sum-of-floored-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-floored-pairs](https://leetcode.cn/problems/sum-of-floored-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,5,9]', '[7,7,7,7,7,7,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int: \n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        res = 0\n",
    "        maxv = max(nums)\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == 1:\n",
    "                res = (res + s) % MOD \n",
    "            else:\n",
    "                for j in range(1, maxv//x + 1):\n",
    "                    v1, v2 = j * x, (j+1) * x - 1\n",
    "                    p1 = bisect_left(nums, v1)\n",
    "                    p2 = bisect_right(nums, v2)\n",
    "                    res = (res + j * (p2 - p1)) % MOD \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int: \n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        res = 0\n",
    "        maxv = max(nums)\n",
    "        prev = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == 1:\n",
    "                res = (res + s) % MOD \n",
    "            else:\n",
    "                if i > 0 and x == nums[i-1]: \n",
    "                    res = (res + prev) % MOD \n",
    "                    continue\n",
    "                prev = 0\n",
    "                for j in range(1, maxv//x + 1):\n",
    "                    v1, v2 = j * x, (j+1) * x - 1\n",
    "                    p1 = bisect_left(nums, v1)\n",
    "                    p2 = bisect_right(nums, v2)\n",
    "                    res = (res + j * (p2 - p1)) % MOD \n",
    "                    prev += j * (p2 - p1)\n",
    "                \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = max(nums)\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(len(nums)):\n",
    "            dp[nums[i]] += 1\n",
    "        for i in range(1, n+1):\n",
    "            dp[i] += dp[i-1]\n",
    "        for i in range(1, n+1):\n",
    "            cnt = dp[i] - dp[i-1]\n",
    "            if not cnt:\n",
    "                continue\n",
    "            for d in range(1, n//i + 1):\n",
    "                right = i * (d+1) -1 if i *(d+1)-1<=n else n\n",
    "                left = i * d\n",
    "                number = dp[right] - dp[left-1]\n",
    "                res += number * cnt * d\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        n = max(nums)\n",
    "\n",
    "        # 数字计数\n",
    "        cnt = [0] * (n + 1)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        # 数字的前缀计数即cnt[i]为小于等于i的个数\n",
    "        for i in range(1, n + 1):\n",
    "            cnt[i] += cnt[i - 1]\n",
    "\n",
    "        ans = 0\n",
    "        # 枚举分母y的数值从[1, n]\n",
    "        for y in range(1, n + 1):\n",
    "            # 对应分母y的个数\n",
    "            denominator = cnt[y] - cnt[y - 1]\n",
    "            if denominator:\n",
    "                # 枚举d的范围从[1, n//y]\n",
    "                for d in range(1, n // y + 1):\n",
    "                    # x//y=d当中的分子x落在区间[left, right]范围内\n",
    "                    right = y * (d + 1) - 1 if y * (d + 1) - 1 < n else n\n",
    "                    left = y * d\n",
    "                    # 计算分子x的个数\n",
    "                    numerator = cnt[right] - cnt[left - 1]\n",
    "                    # 分子x的个数*分母y的个数*商d的值\n",
    "                    ans += d * numerator * denominator\n",
    "                    ans %= MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        n = len(nums)\n",
    "        maxNum = max(nums)\n",
    "        counter = [0] * (maxNum + 1)\n",
    "        for num in nums:\n",
    "            counter[num] += 1 \n",
    "        for i in range(1, maxNum + 1):\n",
    "            counter[i] += counter[i - 1]\n",
    "        res = 0\n",
    "        for i in range(1, maxNum + 1):\n",
    "            if counter[i] - counter[i - 1] == 0:\n",
    "                continue\n",
    "            x = 1 \n",
    "            while x * i <= maxNum:\n",
    "                res += x * (counter[i] - counter[i - 1]) * (counter[min(maxNum, (x + 1) * i - 1)] - counter[max(0, x * i - 1)])\n",
    "                x += 1 \n",
    "                res %= 10 ** 9 + 7\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 元素最大值\n",
    "        upper = max(nums)\n",
    "        cnt = [0] * (upper + 1)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        # 预处理前缀和\n",
    "        pre = [0] * (upper + 1)\n",
    "        for i in range(1, upper + 1):\n",
    "            pre[i] = pre[i - 1] + cnt[i]\n",
    "        \n",
    "        ans = 0\n",
    "        for y in range(1, upper + 1):\n",
    "            # 一个小优化，如果数组中没有 y 可以跳过\n",
    "            if cnt[y]:\n",
    "                d = 1\n",
    "                while d * y <= upper:\n",
    "                    ans += cnt[y] * d * (pre[min((d + 1) * y - 1, upper)] - pre[d * y - 1])\n",
    "                    d += 1\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        mod = int(1e9+7)\n",
    "        upper = max(nums)\n",
    "        cnt = [0] * (upper + 1)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        pre = [0] * (upper + 1)\n",
    "        for i in range(1, upper + 1):\n",
    "            pre[i] = pre[i-1] + cnt[i]\n",
    "        ans = 0\n",
    "        for y in range(1, upper + 1):\n",
    "            if cnt[y]:\n",
    "                d = 1\n",
    "                while d * y <= upper:\n",
    "                    ans += cnt[y] * d * (pre[min((d+1)*y-1,upper)] - pre[d*y-1])\n",
    "                    d += 1\n",
    "        return ans % mod "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        maxn = int(1e5 + 5)\n",
    "        sum = 0\n",
    "        num = [0] * maxn\n",
    "        for i in nums:\n",
    "            num[i] = num[i] + 1\n",
    "        sumnum = [0] * maxn\n",
    "        for i in range(1, maxn):\n",
    "            sumnum[i] = num[i] + sumnum[i - 1]\n",
    "        for i in range(1, maxn):\n",
    "            if num[i] != 0:\n",
    "                for j in range(i, maxn, i):\n",
    "                    t = min(j + i - 1, maxn - 1)\n",
    "                    sum = sum + num[i] * j / i * (sumnum[t] - sumnum[j - 1])\n",
    "        return int(sum % int(1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        n = 10**5\n",
    "        mod = 10**9 + 7\n",
    "        cnt = [0] * (n + 1)\n",
    "        upper = 1\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "            upper = max(num, upper)\n",
    "        pref_cnt = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            pref_cnt[i] = pref_cnt[i-1] + cnt[i]\n",
    "        \n",
    "        res = 0\n",
    "        for y in range(1, upper+1):\n",
    "            if cnt[y] != 0:\n",
    "                d = 1\n",
    "                while d * y <= upper:\n",
    "                    res += (pref_cnt[min(upper, (d+1)*y-1)] - pref_cnt[d*y-1]) * d * cnt[y]\n",
    "                    d += 1\n",
    "        return res % mod\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 元素最大值\n",
    "        upper = max(nums)\n",
    "        cnt = [0] * (upper + 1)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        # 预处理前缀和\n",
    "        pre = [0] * (upper + 1)\n",
    "        for i in range(1, upper + 1):\n",
    "            pre[i] = pre[i - 1] + cnt[i]\n",
    "        \n",
    "        ans = 0\n",
    "        for y in range(1, upper + 1):\n",
    "            # 一个小优化，如果数组中没有 y 可以跳过\n",
    "            if cnt[y]:\n",
    "                d = 1\n",
    "                while d * y <= upper:\n",
    "                    ans += cnt[y] * d * (pre[min((d + 1) * y - 1, upper)] - pre[d * y - 1])\n",
    "                    d += 1\n",
    "        return ans % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 元素最大值\n",
    "        upper = max(nums)\n",
    "        cnt = [0] * (upper + 1)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        # 预处理前缀和\n",
    "        pre = [0] * (upper + 1)\n",
    "        for i in range(1, upper + 1):\n",
    "            pre[i] = pre[i - 1] + cnt[i]\n",
    "        \n",
    "        ans = 0\n",
    "        for y in range(1, upper + 1):\n",
    "            # 一个小优化，如果数组中没有 y 可以跳过\n",
    "            if cnt[y]:\n",
    "                d = 1\n",
    "                while d * y <= upper:\n",
    "                    ans += cnt[y] * d * (pre[min((d + 1) * y - 1, upper)] - pre[d * y - 1])\n",
    "                    d += 1\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 元素最大值\n",
    "        upper = max(nums)\n",
    "        cnt = [0] * (upper + 1)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        # 预处理前缀和\n",
    "        pre = [0] * (upper + 1)\n",
    "        for i in range(1, upper + 1):\n",
    "            pre[i] = pre[i - 1] + cnt[i]\n",
    "        \n",
    "        ans = 0\n",
    "        for y in range(1, upper + 1):\n",
    "            # 一个小优化，如果数组中没有 y 可以跳过\n",
    "            if cnt[y]:\n",
    "                d = 1\n",
    "                while d * y <= upper:\n",
    "                    ans += cnt[y] * d * (pre[min((d + 1) * y - 1, upper)] - pre[d * y - 1])\n",
    "                    d += 1\n",
    "        return ans % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        maxn = int(1e5 + 5)\n",
    "        sum = 0\n",
    "        num = [0] * maxn\n",
    "        for i in nums:\n",
    "            num[i] = num[i] + 1\n",
    "        sumnum = [0] * maxn\n",
    "        for i in range(1, maxn):\n",
    "            sumnum[i] = num[i] + sumnum[i - 1]\n",
    "        for i in range(1, maxn):\n",
    "            if num[i] != 0:\n",
    "                for j in range(i, maxn, i):\n",
    "                    t = min(j + i - 1, maxn - 1)\n",
    "                    sum = sum + num[i] * j / i * (sumnum[t] - sumnum[j - 1])\n",
    "        return int(sum % int(1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        max_num = max(nums)\n",
    "        cnt = [0] * (max_num + 1)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        pre = [0] * (max_num + 1)\n",
    "        for i in range(1, max_num + 1):\n",
    "            pre[i] = pre[i - 1] + cnt[i]\n",
    "        res = 0\n",
    "        for y in range(1, max_num + 1):\n",
    "            if cnt[y] == 0:\n",
    "                continue\n",
    "            d = 1\n",
    "            while d * y <= max_num:\n",
    "                res += cnt[y] * d * (pre[min((d + 1) * y - 1, max_num)] - pre[d * y - 1])\n",
    "                d += 1\n",
    "        return res % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        upper = max(nums)\n",
    "        cnt = [0] * (upper + 1)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        pres = [0] * (upper + 1)\n",
    "        for i in range(1, upper + 1):\n",
    "            pres[i] += pres[i - 1] + cnt[i]\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        for i in range(1, upper + 1):\n",
    "\n",
    "            if cnt[i]:\n",
    "                d = 1\n",
    "                while d * i <= upper:\n",
    "                    ans += cnt[i] * d * (pres[min((d + 1) * i - 1, upper)] - pres[d * i - 1])\n",
    "\n",
    "                    d += 1\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        upper = max(nums)\n",
    "        MOD = 10**9+7\n",
    "        ret = 0\n",
    "        counter = [0] * (upper + 1)\n",
    "        for n in nums:\n",
    "            counter[n] += 1\n",
    "        pre = [0] * (upper+1)\n",
    "        for i in range(1, upper+1):\n",
    "            pre[i] = pre[i-1] + counter[i]\n",
    "\n",
    "        for y in range(1, upper + 1):\n",
    "            d = 1\n",
    "            while d * y <= upper:\n",
    "                ret += counter[y] * d * (pre[min((d+1)*y-1, upper)] - pre[d*y-1])\n",
    "                d += 1\n",
    "        return ret % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        max_num = max(nums)\n",
    "        cnt = [0] * (max_num + 1)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        pre = list(accumulate(cnt))\n",
    "        ans = 0\n",
    "        for num, x in enumerate(cnt):\n",
    "            if x == 0:\n",
    "                continue\n",
    "            for k in range(1, max_num // num + 1):\n",
    "                l, r = k * num, min(max_num, (k + 1) * num - 1)\n",
    "                ans = (ans + x * k * (pre[r] - pre[l - 1])) % mod\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        upper = max(nums)\n",
    "        cnt = [0] * (upper+1)\n",
    "        for i in range(len(nums)):\n",
    "            cnt[nums[i]] += 1\n",
    "        presum = [0] * (upper+1)\n",
    "        for i in range(1, upper+1):\n",
    "            presum[i] = presum[i-1] + cnt[i]\n",
    "        res = 0\n",
    "        for y in range(1, upper+1):\n",
    "            if cnt[y]:\n",
    "                k = 1\n",
    "                while k * y <= upper:\n",
    "                    res += cnt[y] * k * (presum[min((k+1)*y-1, upper)] - presum[k*y-1])\n",
    "                    k += 1\n",
    "        return res %(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        m = max(nums)\n",
    "        cnter = [0]*(m+1)\n",
    "        for n in nums:\n",
    "            cnter[n] += 1\n",
    "        presums = list(itertools.accumulate(cnter))\n",
    "\n",
    "        MOD = 10**9+7\n",
    "        res = 0\n",
    "        for n in range(1,m+1):\n",
    "            if cnter[n]:\n",
    "                d = 1\n",
    "                while d*n <= m:\n",
    "                    res = (res+cnter[n]*d*(presums[min((d+1)*n-1,m)]-presums[d*n-1]))%MOD\n",
    "                    d += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 元素最大值\n",
    "        upper = max(nums)\n",
    "        cnt = [0] * (upper + 1)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        # 预处理前缀和\n",
    "        pre = [0] * (upper + 1)\n",
    "        for i in range(1, upper + 1):\n",
    "            pre[i] = pre[i - 1] + cnt[i]\n",
    "        \n",
    "        ans = 0\n",
    "        for y in range(1, upper + 1):\n",
    "            # 一个小优化，如果数组中没有 y 可以跳过\n",
    "            if cnt[y]:\n",
    "                d = 1\n",
    "                while d * y <= upper:\n",
    "                    ans += cnt[y] * d * (pre[min((d + 1) * y - 1, upper)] - pre[d * y - 1])\n",
    "                    d += 1\n",
    "        return ans % mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        upper = max(nums)\n",
    "        cnt = [0] * (upper + 1)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        presum = [0] * (upper + 1)\n",
    "        for i in range(1, upper+1):\n",
    "            presum[i] = presum[i-1] + cnt[i]\n",
    "        res = 0\n",
    "        for y in range(1, upper + 1):\n",
    "            if cnt[y]:\n",
    "                k = 1\n",
    "                while k * y <= upper:\n",
    "                    res += cnt[y] * k * (presum[min(upper, (k+1)*y-1)] - presum[k*y-1])\n",
    "                    k += 1\n",
    "        return res % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        # 元素最大值\n",
    "        upper = max(nums)\n",
    "        # 记录每个元素出现的频次\n",
    "        cnt = [0] * (upper + 1)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        # 预处理 cnt 数组的前缀和\n",
    "        pre = [0] * (upper + 1)\n",
    "        for i in range(1, upper + 1):\n",
    "            pre[i] = cnt[i] + pre[i - 1]\n",
    "        \n",
    "        res = 0\n",
    "        # 对每个出现在 nums 中的值 y, 遍历 d = floor(x / y)\n",
    "        # 最后的结果应该是 d * cnt[x] * cnt[y] 的和\n",
    "        # 遍历 y\n",
    "        for y in range(1, upper + 1):\n",
    "            if cnt[y]:  # 跳过那些没有出现在 nums 中的 y\n",
    "                # 遍历 d = floor(x / y)\n",
    "                d = 1\n",
    "                while d * y <= upper:\n",
    "                    res += cnt[y] * d * (pre[min((d + 1) * y - 1, upper)] - pre[d * y - 1])\n",
    "                    d += 1\n",
    "        return res % mod\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        max_num = max(nums)\n",
    "        cnt = [0] * (max_num + 1)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        pre = list(accumulate(cnt))\n",
    "        ans = 0\n",
    "        for num, x in enumerate(cnt):\n",
    "            if x == 0:\n",
    "                continue\n",
    "            for k in range(1, max_num // num + 1):\n",
    "                l, r = k * num, min(max_num, (k + 1) * num - 1)\n",
    "                ans = (ans + x * k * (pre[r] - pre[l - 1])) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int: \n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        s = list(accumulate(nums, initial = 0))\n",
    "        MOD = 10 ** 9 + 7\n",
    "        res = 0\n",
    "        maxv = max(nums)\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == 1:\n",
    "                res = (res + s[n]) % MOD \n",
    "            else:\n",
    "                for j in range(1, maxv//x + 1):\n",
    "                    v1, v2 = j * x, (j+1) * x - 1\n",
    "                    p1 = bisect_left(nums, v1)\n",
    "                    p2 = bisect_right(nums, v2)\n",
    "                    res = (res + j * (p2 - p1)) % MOD \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        MX = 2*(10**5)\n",
    "        cnt = [0]*MX\n",
    "        for num in nums:\n",
    "            cnt[num]+=1\n",
    "        pref = [0] * (MX+1)\n",
    "        for k,v in enumerate(cnt):\n",
    "            pref[k+1] = pref[k] + v\n",
    "        # print(pref[:20])\n",
    "        ans = 0\n",
    "        MOD = 10**9+7\n",
    "        for k,v in enumerate(cnt):\n",
    "            if v<=0:continue\n",
    "            for x in range(1,10**5+1):\n",
    "                if x*k>10**5:\n",
    "                    break\n",
    "              \n",
    "                # 分母 * 商 * 分子个数\n",
    "                # ans += v*x*(pref[(x+1)*k]-pref[x*k])\n",
    "                try:\n",
    "                    # print(k,x,(x+1)*k,x*k,pref[(x+1)*k]-pref[x*k])\n",
    "                    ans = (v*x*(pref[(x+1)*k]-pref[x*k]) + ans) % MOD\n",
    "                except:\n",
    "                    print((x+1)*k,x,k)\n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        cnt = [0] * 200005\n",
    "        for x in nums:\n",
    "            cnt[x] += 1\n",
    "        s = [0]\n",
    "        for x in cnt:\n",
    "            s.append(s[-1] + x)\n",
    "        ans = 0\n",
    "        for i, x in enumerate(cnt):\n",
    "            if x > 0 :\n",
    "                # d * y <= x < (d + 1) * y\n",
    "                for d in range(1, 100000 // i + 1):\n",
    "                    ans += x * d * (s[(d + 1) * i] - s[d * i])\n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        cnts = Counter(nums)\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        for num in sorted(cnts.keys()):\n",
    "            a = 1\n",
    "            l = bisect.bisect_left(nums,num)\n",
    "            while l < n:\n",
    "                if (a + 1) * num < nums[l]:\n",
    "                    a = nums[l] // num\n",
    "                    continue\n",
    "                else:\n",
    "                    a += 1\n",
    "                r = bisect.bisect_left(nums,a * num)\n",
    "                ans += (r - l) * (a - 1) * cnts[num]\n",
    "                l = r\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        pre, result, MOD = [0] * ((m := max(nums)) + 1), 0, 10 ** 9 + 7\n",
    "        for num in nums:\n",
    "            pre[num] += 1\n",
    "        for i in range(m):\n",
    "            pre[i + 1] += pre[i]\n",
    "        for num in set(nums):\n",
    "            for d in range(1, m // num + 1):\n",
    "                result += (pre[min((d + 1) * num - 1, m)] - pre[d * num - 1]) * d * (pre[num] - pre[num - 1])\n",
    "        return result % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        nums.sort()#排序\n",
    "        l = len(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        d = {}#数字统计\n",
    "        for n in nums:\n",
    "            d[n] = d.get(n, 0) + 1\n",
    "        for n in d.keys():\n",
    "            r = bisect.bisect_left(nums, n)#找到大于等于n的索引\n",
    "            t = 1#倍数\n",
    "            while r < l:\n",
    "                if nums[r] > (t + 1) * n:#当下一个数字太大，直接将倍数进行调整\n",
    "                    t = nums[r] // n\n",
    "                    continue\n",
    "                else:#否则倍数+1\n",
    "                    t = t + 1\n",
    "                tmp = bisect.bisect_left(nums, n * t)#下一个倍数的索引\n",
    "                res += (t - 1) * (tmp - r) * d[n]#两个索引之间的数字数量就是前一个倍数的数字数量，再乘以本数字的数量\n",
    "                r = tmp\n",
    "                res %= mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        maxn = int(1e5 + 5)\n",
    "        sum = 0\n",
    "        num = [0] * maxn * 2\n",
    "        for i in nums:\n",
    "            num[i] = num[i] + 1\n",
    "        sumnum = [0] * maxn * 2\n",
    "        for i in range(1, maxn * 2):\n",
    "            sumnum[i] = num[i] + sumnum[i - 1]\n",
    "        for i in range(1, maxn):\n",
    "            if num[i] != 0:\n",
    "                for j in range(i, maxn, i):\n",
    "                    #print(i, j, num[i], sumnum[j], sumnum[j + i - 1])\n",
    "                    sum = sum + num[i] * j / i * (sumnum[j + i - 1] - sumnum[j - 1])\n",
    "        return int(sum % int(1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        maximum,res=max(nums),0\n",
    "        cumsum=[0 for i in range(maximum+1)]\n",
    "        for i in nums:\n",
    "            cumsum[i]+=1\n",
    "        for i in range(1, len(cumsum)):\n",
    "            cumsum[i]+=cumsum[i-1]\n",
    "        for i in set(nums):\n",
    "            for j in range(1,maximum//i+1):\n",
    "                res+=(cumsum[min((j+1)*i-1,maximum)]-cumsum[j*i-1])*j*(cumsum[i]-cumsum[i-1])\n",
    "        return res%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        upper = max(nums)\n",
    "        cnt = [0] * (upper + 1)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        pres = [0] * (upper + 1)\n",
    "        for i in range(1, upper + 1):\n",
    "            pres[i] += pres[i - 1] + cnt[i]\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        for i in set(nums):\n",
    "\n",
    "            if cnt[i]:\n",
    "                d = 1\n",
    "                while d * i <= upper:\n",
    "                    ans += cnt[i] * d * (pres[min((d + 1) * i - 1, upper)] - pres[d * i - 1])\n",
    "\n",
    "                    d += 1\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        maxnum = max(nums)\n",
    "\n",
    "        c = [0 for _ in range(maxnum + 1)]\n",
    "        for num in nums:\n",
    "            c[num] += 1\n",
    "        \n",
    "        p = [0 for _ in range(maxnum + 1)]\n",
    "        for i in range(1, maxnum + 1):\n",
    "            p[i] = p[i - 1] + c[i]\n",
    "        \n",
    "        ans = 0 \n",
    "        for num in set(nums):\n",
    "            d = 1\n",
    "            while d * num <= maxnum:\n",
    "                ans += c[num] * d * (p[min((d + 1) * num - 1, maxnum)] - p[d * num - 1])\n",
    "                # ans %= mod\n",
    "                d += 1\n",
    "        return ans % mod\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        maxnum = max(nums)\n",
    "\n",
    "        c = [0 for _ in range(maxnum + 1)]\n",
    "        for num in nums:\n",
    "            c[num] += 1\n",
    "        \n",
    "        p = [0 for _ in range(maxnum + 1)]\n",
    "        for i in range(1, maxnum + 1):\n",
    "            p[i] = p[i - 1] + c[i]\n",
    "        \n",
    "        ans = 0 \n",
    "        for num in set(nums):\n",
    "            d = 1\n",
    "            while d * num <= maxnum:\n",
    "                ans += c[num] * d * (p[min((d + 1) * num - 1, maxnum)] - p[d * num - 1])\n",
    "                ans %= mod\n",
    "                d += 1\n",
    "        return ans % mod\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        maxn,res, mod = int(2e5+5),0,int(1e9 + 7)\n",
    "        cnt = [0 for _ in range(maxn)]\n",
    "        for num in nums: cnt[num]+=1\n",
    "        sum = [0]+list(itertools.accumulate(cnt))\n",
    "        for i,c in enumerate(cnt):\n",
    "            if c:\n",
    "                d=1\n",
    "                while i*(d+1)<=maxn:\n",
    "                    res+=c*d*(sum[(d+1)*i]-sum[d*i])%mod\n",
    "                    d+=1 \n",
    "        return res%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1000000007\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        nums = list(cnt.keys())\n",
    "        n = max(nums)\n",
    "        pre = [0] * (n + 1)\n",
    "        for num in nums:\n",
    "            pre[num] += cnt[num]\n",
    "        for i in range(1, n + 1):\n",
    "            pre[i] += pre[i - 1]\n",
    "\n",
    "        ans = 0\n",
    "        for num in cnt:\n",
    "            x = 1\n",
    "            while x * num <= n:\n",
    "                low = x * num\n",
    "                high = (x + 1) * num - 1 if (x + 1) * num - 1 <= n else n\n",
    "                ans += cnt[num] * x * (pre[high] - pre[low - 1])\n",
    "                ans %= MOD\n",
    "                x += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        c = Counter(nums)\n",
    "        m = max(nums)\n",
    "        f = [0] * (m + 2)\n",
    "        for i in range(m, -1, -1):\n",
    "            f[i] = f[i + 1] + c[i]\n",
    "        ans = 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, m // i + 1):\n",
    "                ans += f[i * j] * c[i]\n",
    "            ans %= (10 ** 9 + 7)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        numfre = defaultdict(int)\n",
    "        maxnums=max(nums)\n",
    "        for num in nums:\n",
    "            numfre[num]+=1\n",
    "        prefixcount = [0]\n",
    "        for i in range(maxnums*2+1):\n",
    "            if i in numfre:\n",
    "                prefixcount.append(prefixcount[-1]+numfre[i])\n",
    "            else:\n",
    "                prefixcount.append(prefixcount[-1])\n",
    "        # print(prefixcount)\n",
    "        sumfloor = 0\n",
    "        # num =2  i=1  prefixcount[4]-prefixcount[2]\n",
    "        \n",
    "        for num in numfre:\n",
    "            i=1\n",
    "            while num*i<=maxnums:\n",
    "                sumfloor += numfre[num]*i*(prefixcount[num*(i+1)]-prefixcount[num*i])\n",
    "                sumfloor%=(10**9+7)\n",
    "                # print(num,numfre[num],i,(prefixcount[num*(i+1)+1]-prefixcount[num*i]))\n",
    "                i+=1\n",
    "        return sumfloor%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        for x in nums:\n",
    "            cnt[x] += 1\n",
    "\n",
    "        mx = max(cnt)\n",
    "        pres = [0] * (mx + 2)\n",
    "        for x in range(mx+1):\n",
    "            pres[x+1] = pres[x] + cnt.get(x, 0)\n",
    "\n",
    "        ans = 0\n",
    "        for x, c in cnt.items():\n",
    "            for d in range(1, mx//x+1):\n",
    "                ans += c * d * (pres[min((d+1)*x, mx+1)] - pres[d*x])\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        cnts = Counter(nums)\n",
    "        n = len(cnts)\n",
    "        MOD = int(1e9) + 7\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        hi = max(nums)\n",
    "        pres = list(accumulate(cnts[x] if x in cnts else 0 for x in range(hi + 1)))\n",
    "\n",
    "        for i in range(1, hi + 1):\n",
    "            if i in cnts:\n",
    "                j = 1\n",
    "\n",
    "                while i * j <= hi:\n",
    "                    ret = (ret + cnts[i] * (pres[min((j + 1) * i - 1, hi)] - pres[j * i - 1]) * j) % MOD\n",
    "\n",
    "                    j += 1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\r\n",
    "class Solution:\r\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\r\n",
    "        cnt = Counter(nums)\r\n",
    "        m = max(cnt.keys())\r\n",
    "        presum = [0] * (m + 1)\r\n",
    "        for i in range(m):\r\n",
    "            presum[i + 1] = presum[i]\r\n",
    "            if i + 1 in cnt:\r\n",
    "                presum[i + 1] += cnt[i + 1]\r\n",
    "        \r\n",
    "        res = 0\r\n",
    "        for i in range(1, m + 1):\r\n",
    "            if i not in cnt: continue\r\n",
    "            for d in range(1, m // i + 1):\r\n",
    "                res += cnt[i] * d * (presum[min((d + 1) * i - 1, m)] - presum[d * i - 1])\r\n",
    "        \r\n",
    "        return res % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        m = Counter(nums)\n",
    "        maxl = max(nums)\n",
    "        pre = [0] * (maxl + 1)\n",
    "        for i in range(1, maxl + 1):\n",
    "            pre[i] = pre[i - 1] + m[i]\n",
    "        res = 0\n",
    "        for num in m:\n",
    "            i = 1\n",
    "            while i * num <= maxl:\n",
    "                if maxl < (i + 1) * num - 1:\n",
    "                    res = (res + (pre[-1] - pre[i * num - 1]) * i * m[num]) % (10 ** 9 + 7)\n",
    "                else:\n",
    "                    res = (res + (pre[(i + 1) * num - 1] - pre[i * num - 1]) * i * m[num]) % (10 ** 9 + 7)\n",
    "                i += 1 \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        numfre = defaultdict(int)\n",
    "        maxnums=max(nums)\n",
    "        for num in nums:\n",
    "            numfre[num]+=1\n",
    "        prefixcount = [0]\n",
    "        for i in range(1,maxnums+1):\n",
    "            if i in numfre:\n",
    "                prefixcount.append(prefixcount[-1]+numfre[i])\n",
    "            else:\n",
    "                prefixcount.append(prefixcount[-1])\n",
    "        # print(prefixcount)\n",
    "        sumfloor = 0\n",
    "        # num =2  i=1  prefixcount[4]-prefixcount[2]\n",
    "        \n",
    "        for num in numfre:\n",
    "            i=1\n",
    "            while num*i<=maxnums:\n",
    "                sumfloor += numfre[num]*i*(prefixcount[min(num*(i+1)-1,maxnums)]-prefixcount[num*i-1])\n",
    "                sumfloor%=(10**9+7)\n",
    "                # print(num,numfre[num],i,(prefixcount[min(num*(i+1)-1,maxnums)]-prefixcount[num*i-1]))\n",
    "                i+=1\n",
    "        return sumfloor%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        count = Counter(nums)\n",
    "        max_val = max(nums)\n",
    "        presum = [0]\n",
    "        for i in range(1, max_val + 1):\n",
    "            presum.append(presum[-1] + count[i])\n",
    "\n",
    "        ans = 0\n",
    "        for x in range(1, max_val + 1):\n",
    "            if not count[x]:\n",
    "                continue\n",
    "            multiple = x\n",
    "            while multiple <= max_val:\n",
    "                ans += count[x] * multiple // x * (presum[min(multiple + x - 1, max_val)] - presum[multiple - 1])                \n",
    "                multiple += x\n",
    "\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        # 1 2 3 4 5 6 7 8 9 10\n",
    "        MOD = 10**9 + 7\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        numcnt=[0]*(2*nums[-1]) # <=n\n",
    "        cnt=0\n",
    "        index=0\n",
    "        for _ in nums:\n",
    "            while index<_:\n",
    "                numcnt[index]=cnt\n",
    "                index+=1\n",
    "            cnt+=1\n",
    "        while index<len(numcnt):\n",
    "            numcnt[index]=cnt\n",
    "            index+=1\n",
    "        # print(nums, numcnt)\n",
    "        res=0\n",
    "        for i, k in Counter(nums).items():\n",
    "            for j in range(i, nums[-1]+1, i):\n",
    "                # print(i,j,numcnt[j+i-1],numcnt[j-1],count[j])\n",
    "                res+= k*(j//i)*(numcnt[j+i-1] - numcnt[j-1])\n",
    "                res%= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        # 1 2 3 4 5 6 7 8 9 10\n",
    "        MOD = 10**9 + 7\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        numcnt=[0]*(2*nums[-1]) # <=n\n",
    "        cnt=0\n",
    "        index=0\n",
    "        for _ in nums:\n",
    "            while index<_:\n",
    "                numcnt[index]=cnt\n",
    "                index+=1\n",
    "            cnt+=1\n",
    "        while index<len(numcnt):\n",
    "            numcnt[index]=cnt\n",
    "            index+=1\n",
    "        # print(nums, numcnt)\n",
    "        res=0\n",
    "        for i, k in Counter(nums).items():\n",
    "            for j in range(i, nums[-1]+1, i):\n",
    "                # print(i,j,numcnt[j+i-1],numcnt[j-1],count[j])\n",
    "                res+= k*(j//i)*(numcnt[j+i-1] - numcnt[j-1])\n",
    "                res%= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfFlooredPairs(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        cnt = Counter(nums)\n",
    "        mx = nums[-1]\n",
    "        ans = 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        for num in set(nums):\n",
    "            st = 1\n",
    "            while st * num <= mx:\n",
    "                l = bisect.bisect_left(nums, st * num)\n",
    "                r = bisect.bisect_left(nums, (st + 1) * num)\n",
    "                ans = (ans + (r - l) * st * cnt[num]) % mod\n",
    "                st += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
